package org.korifey.ffalg;

import static org.junit.Assert.*;

import java.security.SecureRandom;
import java.util.Random;

import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;
import static org.korifey.ffalg.NumberTheory.*;

public class NumberTheoryTest {
		
	static int[] primes;
	
	@BeforeClass
	public static void setUp() {
		primes = erathosphen(10000000);
	}
	
	@Test
	public void testUpperLimitOfPrimes() {
		for (int i=0; i< primes.length; i++) {
			if (upperLimitOfPrimes(primes[i]) < i) {
				fail();
			}
		}
	}
	
	@Test
	public void testGcd() {
		assertEquals(1, gcd(10, 11));
		assertEquals(2, gcd(1002, 1006));
		assertEquals(3, gcd(21, 15));
	}
	
	@Test
	public void testGcdExt() {		
		
		long[][] valuesToTest = new long [][] {{1,1}, {2, 1}, {1, 2}, {3, 4}, {1000, 1550}
			,{Integer.MAX_VALUE, Integer.MAX_VALUE-1}, {Integer.MAX_VALUE, Integer.MAX_VALUE}
			,{primes[primes.length-1], primes[primes.length-2]}};		
		for (long[] v: valuesToTest) {
			long a = v[0];
			long b = v[1];
			GcdExtResult res = gcdExt(a, b);
			assertEquals(gcd(a, b), res.gcd());
			assertEquals(String.format("Error on test data (%d, %d)", a, b), res.gcd(), a*res.x()+b*res.y());
		}		
	}
	
	@Test
	public void testGcdExtRandom() {
		Random r = new SecureRandom();
		for (int i=0; i<10; i++) {
			long a = r.nextInt(Integer.MAX_VALUE)+1l;
			long b = r.nextInt(Integer.MAX_VALUE)+1l;
			GcdExtResult res = gcdExt(a, b);
			assertEquals(gcd(a, b), res.gcd());
			assertEquals(String.format("Error on test data (%d, %d)", a, b), res.gcd(), a*res.x()+b*res.y());
		}
	}
	
	@Test
	public void testModEquationNoSolution() {
		assertEquals(null, solveModEquation(0, 1, 2));
		assertEquals(null, solveModEquation(2, 1, 2));
		assertEquals(null, solveModEquation(6, 2, 3));
		
		assertEquals(null, solveModEquation(5, 6, 10));		
	}
	
	private static void testModEquation(long a, long b, long c) {
		AffineFunction res = solveModEquation(a, b, c);
		
		for (long x = -1000; x <= 1000; x++) {
			if ((a*x - b) % c == 0) {
				if (res == null || !res.containsValue(x)) {
					fail(String.format("Solve of equation %s*x = %x (mod %s) must contain %s, but solve is: %s", a, b, c, x, res));
				}

			} else {
				if (res != null && res.containsValue(x)) {			
					fail(String.format("Solve of equation %s*x = %x (mod %s) must NOT contain %s, but solve is: %s", a, b, c, x, res));
				}	
			}			
		}
	}
	
	
	@Test
	public void testModEquationOneSolution() {
		testModEquation(2, 2, 3);
		testModEquation(15, 10, 20);
			
	}
	
	@Test
	public void testModEquationMultipleSolution() {
		solveModEquation(2, 2, 2);
		testModEquation(0, 3, 3);
		testModEquation(0, 4, 4);
		testModEquation(6, 2, 4);
		testModEquation(11, 1, 13);
		testModEquation(11, 2, 13);
	}
}
